package com.yiwenup.struct._02_tree.bst.bbst.base;

import com.yiwenup.struct._02_tree.bst.BinarySearchTree;

import java.util.Comparator;

/**
 * 平衡二叉搜索树
 **/
public class BalancedBinarySearchTree<E> extends BinarySearchTree<E> {
    public BalancedBinarySearchTree() {
        this(null);
    }

    public BalancedBinarySearchTree(Comparator<E> comparator) {
        super(comparator);
    }

    protected void rotateLeft(Node<E> g) {
        Node<E> p = g.right;
        Node<E> t1 = p.left;
        g.right = t1;
        p.left = g;

        afterRotate(g, p, t1);
    }

    protected void rotateRight(Node<E> g) {
        Node<E> p = g.left;
        Node<E> t2 = p.right;
        g.left = t2;
        p.right = g;

        afterRotate(g, p, t2);
    }

    protected void afterRotate(Node<E> g, Node<E> p, Node<E> t) {
        // 使P成为子树的根节点
        p.parent = g.parent;
        if (g.isLeftChild()) {
            g.parent.left = p;
        } else if (g.isRightChild()) {
            g.parent.right = p;
        } else {
            // g就是整棵树的根节点
            root = p;
        }

        // 使子树的父节点是之前的根节点
        if (t != null) {
            t.parent = g;
        }

        // 使之前根节点的父节点是新的根节点
        g.parent = p;

        // 高度更新
    }

    /**
     * Node r 失衡子树的根节点
     * Node a, b, c 旋转后将成为新的子树的左子树
     * Node d 旋转后将成为新子树的根节点
     * Node e, f, g 旋转后将成为新的子树的右子树
     */
    protected void rotate(Node<E> r,
                          Node<E> a, Node<E> b, Node<E> c,
                          Node<E> d,
                          Node<E> e, Node<E> f, Node<E> g) {
        // 使d成为新子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // a-b-c
        b.left = a;
        b.right = c;
        if (a != null) a.parent = b;
        if (c != null) c.parent = b;

        // e-f-g
        f.left = e;
        f.right = g;
        if (e != null) e.parent = f;
        if (g != null) g.parent = f;

        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
    }
}
